Multithreaded programs are difficult to write, test, and debug. A key reason is nondeterminism: different runs of a multithreaded program may show different behaviors, depending on how the threads interleave. Such multithreading and nondeterminism can cause races, such as data races, atomicity violations, order violations, and any other concurrency errors, in programs.
Two main factors make threads interleave nondeterministically. The first factor, which causes scheduling nondeterminism, is scheduling: how the operating system (OS) and hardware schedule threads. The second factor, which causes input nondeterminism, is input: what data (input, data) arrives at what time (input timing).
A DMT system is, conceptually, a function that maps an input I to a schedule S. The properties of this function are that the same I should map to the same S and that S is a feasible schedule for processing I.
Existing deterministic multithreading (DMT) systems make threads more deterministic by eliminating scheduling nondeterminism. Specifically, such systems constrain a multithreaded program such that it always uses the same thread schedule for the same input. By doing so, these systems make program behaviors repeatable, increase testing confidence, and ease bug reproduction.
Unfortunately, though existing DMT systems eliminate scheduling nondeterminism, they do not reduce input nondeterminism. In fact, they may aggravate the effects of input nondeterminism because of their design limitation: when scheduling the threads to process an input, they consider only this input and ignore previous similar inputs. This stateless design makes schedules over-dependent on inputs, so that a slight change to inputs may force a program to venture into a vastly different, potentially buggy schedule, defeating many benefits of determinism.
In fact, even with the same input, existing DMT systems may still force a program into different schedules for minor changes in the execution environment such as processor type and shared library. Thus, developers may no longer be able to reproduce bugs by running their program on the bug-inducing input, because their machine may differ from the machine where the bug occurred.
Moreover, few existing DMT systems work with server programs whose inputs arrive continuously and non-deterministically.